package com.gxc.integer;

import java.util.HashMap;
import java.util.Map;

/**
 * 3154. 到达第 K 级台阶的方案数

 * 给你有一个 非负 整数 k 。有一个无限长度的台阶，最低 一层编号为 0 。
 *
 * Alice 有一个整数 jump ，一开始值为 0 。Alice 从台阶 1 开始，可以使用 任意 次操作，
 * 目标是到达第 k 级台阶。假设 Alice 位于台阶 i ，一次 操作 中，Alice 可以：
 *
 * 向下走一级到 i - 1 ，但该操作 不能 连续使用，如果在台阶第 0 级也不能使用。
 * 向上走到台阶 i + 2jump 处，然后 jump 变为 jump + 1 。
 * 请你返回 Alice 到达台阶 k 处的总方案数。
 *
 * 注意，Alice 可能到达台阶 k 处后，通过一些操作重新回到台阶 k 处，这视为不同的方案。
 */
public class WaysToReachStair {

    public static void main(String[] args) {
        System.out.println(Math.pow(2, 4));

        System.out.println(handle(0));
        System.out.println(handle(1));
    }

    public static int handle(int k) {
        return recursion(k, 1, 0, 1, new HashMap<>());
    }

    /**
     *
     * @param target
     * @param i
     * @param sub  上一步操作是  -1
     * @param jump
     * @return
     */
    public static int recursion(int target, int i, int sub, int jump, Map<Long, Integer> memo) {
        if (jump == 1073741824) return 0;
        if (i > target+1) return 0;
        //记忆化搜索
        long mask = (long) i << 32 | jump << 1 | sub;
        if (memo.containsKey(mask)) { // 之前算过了
            return memo.get(mask);
        }

        int sum = 0;
        if (i == target) sum++;

        sum += recursion(target, i+jump, 0,  jump * 2, memo);
        //i >0 且 如果上一步不是-1，则可以尝试 -1
        if (i>0 && sub==0) sum += recursion(target, i-1, 1, jump, memo);;

        return sum;
    }

    /**
     * dp[i][j][k] 表示 到达i  2的j次  k 表示上次一是否减法 共有 dp[i]种方法
     * @param k
     * @return
     */
    public static int dp(int k) {
        int[][][] dp = new int[k+1][31][2];


        int sum = 0;
        for (int j = 0; j <= 30; j++) {
            for (int i = 0; i < 2; i++) {
                sum = sum + dp[k][j][i];
            }
        }
        return sum;
    }

    /**
     * 组合
     *
     * [2的n次−n−1,2的n次]
     *
     * m=2的j次−k(npow - k)  -1的次数
     *
     */
    class Solution {
        public int waysToReachStair(int k) {
            int n = 0, npow = 1, ans = 0;
            while (true) {
                if (npow - n - 1 <= k && k <= npow) {
                    ans += comb(n + 1, npow - k);
                } else if (npow - n - 1 > k) {
                    break;
                }
                ++n;
                npow *= 2;
            }
            return ans;
        }

        public int comb(int n, int k) {
            long ans = 1;
            for (int i = n; i >= n - k + 1; --i) {
                ans *= i;
                ans /= n - i + 1;
            }
            return (int) ans;
        }
    }

}
